Pourquoi le traitement d'un tableau trié est-il plus rapide que le traitement d'un tableau non trié?

Vous êtes victime d'un échec de prédiction de branche.
Qu'est-ce que la prédiction de branche?
Considérez une jonction de chemin de fer:
Image de Mecanismo, via Wikimedia Commons. Utilisé sous la licence CC-By-SA 3.0.
Maintenant, pour les besoins de l'argumentation, supposons que ce soit de retour dans les années 1800 - avant les communications longue distance ou radio.
Vous êtes l'opérateur d'un carrefour et vous entendez un train arriver. Vous n'avez aucune idée de la direction que cela doit prendre. Vous arrêtez le train pour demander au chauffeur dans quelle direction il veut. Et puis vous réglez le commutateur de manière appropriée.
Les trains sont lourds et ont beaucoup d'inertie. Ils mettent donc une éternité à démarrer et à ralentir.
Y a-t-il un meilleur moyen? Vous devinez dans quelle direction le train ira!
Si vous avez bien deviné, cela continue.
Si vous vous trompez, le capitaine s'arrête, recule et vous crie de basculer l'interrupteur. Ensuite, il peut redémarrer sur l'autre chemin.
Si vous devinez bien à chaque fois, le train n'aura jamais à s'arrêter. Si vous vous trompez trop souvent, le train passera beaucoup de temps à s'arrêter, à reculer et à redémarrer.
Considérez une instruction if: au niveau du processeur, il s'agit d'une instruction de branchement:
Vous êtes un processeur et vous voyez une succursale. Vous n'avez aucune idée de la direction que cela prendra. Que faire? Vous arrêtez l'exécution et attendez que les instructions précédentes soient terminées. Ensuite, vous continuez sur le bon chemin.
Les processeurs modernes sont compliqués et ont de longs pipelines. Ils mettent donc une éternité à «s'échauffer» et à «ralentir».
Y a-t-il un meilleur moyen? Vous devinez dans quelle direction la branche ira!
Si vous avez bien deviné, vous continuez à exécuter.
Si vous vous trompez, vous devez rincer le pipeline et revenir à la branche. Ensuite, vous pouvez redémarrer sur l'autre chemin.
Si vous devinez juste à chaque fois, l'exécution ne devra jamais s'arrêter. Si vous vous trompez trop souvent, vous passez beaucoup de temps à caler, reculer et redémarrer.
C'est la prédiction de branche. J'admets que ce n'est pas la meilleure analogie puisque le train pourrait simplement indiquer la direction avec un drapeau. Mais dans les ordinateurs, le processeur ne sait pas dans quelle direction une branche ira jusqu'au dernier moment.
Alors, comment devineriez-vous stratégiquement pour minimiser le nombre de fois que le train doit reculer et emprunter l'autre chemin? Vous regardez l'histoire passée! Si le train part à gauche 99% du temps, alors vous devinez à gauche. S'il alterne, alors vous alternez vos suppositions. Si ça va dans un sens toutes les trois fois, vous devinez la même chose ...
En d'autres termes, vous essayez d'identifier un modèle et de le suivre. C'est plus ou moins ainsi que fonctionnent les prédicteurs de branche.
La plupart des applications ont des branches bien comportées. Ainsi, les prédicteurs de branche modernes atteindront généralement des taux de réussite> 90%. Mais face à des branches imprévisibles sans motifs reconnaissables, les prédicteurs de branche sont pratiquement inutiles.
Lectures complémentaires: article "Prédicteur de branche" sur Wikipedia.
Comme indiqué ci-dessus, le coupable est cette déclaration if:
if (données [c]> = 128)
somme + = données [c];
Notez que les données sont uniformément réparties entre 0 et 255. Lorsque les données sont triées, la première moitié des itérations n'entrera pas dans l'instruction if. Après cela, ils entreront tous l'instruction if.
Ceci est très convivial pour le prédicteur de branche puisque la branche va consécutivement dans la même direction plusieurs fois. Même un simple compteur saturant prédira correctement la branche, à l'exception des quelques itérations après avoir changé de direction.
Visualisation rapide:
T = branche prise
N = branche non prise
données [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branche = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (facile à prévoir)
Cependant, lorsque les données sont complètement aléatoires, le prédicteur de branche est rendu inutile, car il ne peut pas prédire des données aléatoires. Ainsi, il y aura probablement environ 50% d'erreurs de prédiction (pas mieux que des suppositions aléatoires).
données [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
branche = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (complètement aléatoire - difficile à prévoir)
Alors qu'est ce qui peut être fait?
Si le compilateur n'est pas en mesure d'optimiser la branche dans un mouvement conditionnel, vous pouvez essayer quelques hacks si vous êtes prêt à sacrifier la lisibilité pour les performances.
Remplacer:
if (données [c]> = 128)
somme + = données [c];
avec:
int t = (données [c] - 128) >> 31;
somme + = ~ t & données [c];
Cela élimine la branche et la remplace par des opérations au niveau du bit.
(Notez que ce hack n'est pas strictement équivalent à l'instruction if d'origine. Mais dans ce cas, il est valable pour toutes les valeurs d'entrée de data [].)
Benchmarks: Core i7 920 à 3,5 GHz
C ++ - Visual Studio 2010 - Version x64
// Branche - Aléatoire
secondes = 11,777
// Branche - Trié
secondes = 2,352
// Sans branche - Aléatoire
secondes = 2,564
// Sans branche - Trié
secondes = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Branche - Aléatoire
secondes = 10,93293813
// Branche - Trié
secondes = 5,643797077
// Sans branches -Aléatoire
secondes = 3.113581453
// Sans branche - Trié
secondes = 3,186068823
Observations:
Avec la branche: Il y a une énorme différence entre les données triées et non triées.
Avec le Hack: Il n'y a aucune différence entre les données triées et non triées.
Dans le cas du C ++, le hack est en fait un peu plus lent qu'avec la branche lorsque les données sont triées.
Une règle générale consiste à éviter le branchement dépendant des données dans les boucles critiques (comme dans cet exemple).
Mise à jour:
GCC 4.6.1 avec -O3 ou -ftree-vectorize sur x64 est capable de générer un déplacement conditionnel. Il n'y a donc aucune différence entre les données triées et non triées - les deux sont rapides.
(Ou un peu rapide: pour le cas déjà trié, cmov peut être plus lent surtout si GCC le met sur le chemin critique au lieu de simplement ajouter, en particulier sur Intel avant Broadwell où cmov a une latence de 2 cycles: l'indicateur d'optimisation gcc -O3 ralentit le code que -O2)
VC ++ 2010 est incapable de générer des déplacements conditionnels pour cette branche, même sous / Ox.
Le compilateur Intel C ++ (ICC) 11 fait quelque chose de miraculeux. Il intervertit les deux boucles, soulevant ainsi la branche imprévisible vers la boucle extérieure. Ainsi, non seulement il est à l'abri des erreurs de prédiction, mais il est également deux fois plus rapide que tout ce que VC ++ et GCC peuvent générer! En d'autres termes, ICC a profité de la boucle de test pour battre le benchmark ...
Si vous donnez au compilateur Intel le code sans branche, il le vectorise juste à droite ... et est tout aussi rapide qu'avec la branche (avec l'échange de boucle).
Cela montre que même les compilateurs modernes matures peuvent varier énormément dans leur capacité à optimiser le code ...
|
Prédiction de branche.
Avec un tableau trié, les données de condition [c]> = 128 sont d'abord fausses pour une série de valeurs, puis deviennent vraies pour toutes les valeurs ultérieures. C'est facile à prévoir. Avec une baie non triée, vous payez les frais de branchement.
|
La raison pour laquelle les performances s'améliorent considérablement lorsque les données sont triées est que la pénalité de prédiction de branche est supprimée, comme expliqué magnifiquement dans la réponse de Mysticial.
Maintenant, si nous regardons le code
if (données [c]> = 128)
somme + = données [c];
nous pouvons constater que la signification de cette branche si ... else ... particulière est d'ajouter quelque chose lorsqu'une condition est satisfaite. Ce type de branche peut être facilement transformé en une instruction de déplacement conditionnelle, qui serait compilée en une instruction de déplacement conditionnelle: cmovl, dans un système x86. La branche et donc la pénalité de prédiction de branche potentielle est supprimée.
En C, donc C ++, l'instruction, qui compilerait directement (sans aucune optimisation) dans l'instruction de déplacement conditionnel de x86, est l'opérateur ternaire ... ...: .... Nous réécrivons donc l'instruction ci-dessus en une déclaration équivalente:
somme + = données [c]> = 128? données [c]: 0;
Tout en conservant la lisibilité, nous pouvons vérifier le facteur d'accélération.
Sur un Intel Core i7-2600K @ 3,4 GHz et Visual Studio 2010 Release Mode, le benchmark est (format copié depuis Mysticial):
x86
// Branche - Aléatoire
secondes = 8,885
// Branche - Trié
secondes = 1,528
// Sans branche - Aléatoire
secondes = 3,716
// Sans branche - Trié
secondes = 3,71
x64
// Branche - Aléatoire
secondes = 11,302
// Branche - Trié
secondes = 1,830
// Sans branche - Aléatoire
secondes = 2,736
// Sans branche - Trié
secondes = 2,737
Le résultat est robuste dans plusieurs tests. Nous obtenons une grande accélération lorsque le résultat de la branche est imprévisible, mais nous souffrons un peu quand il est prévisible. En fait, lors de l'utilisation d'un déplacement conditionnel, les performances sont les mêmes quel que soit le modèle de données.
Regardons maintenant de plus près en examinant l'assemblage x86 qu'ils génèrent. Pour plus de simplicité, nous utilisons deux fonctions max1 et max2.
max1 utilise la branche conditionnelle if ... else ...:
int max1 (int a, int b) {
si (a> b)
return a;
autre
retour b;
}
max2 utilise l'opérateur ternaire ...? ...: ...:
int max2 (int a, int b) {
retourne a> b? un B;
}
Sur une machine x86-64, GCC -S génère l'assemblage ci-dessous.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
laisser
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
laisser
ret
max2 utilise beaucoup moins de code en raison de l'utilisation de l'instruction cmovge. Mais le vrai gain est que max2 n'implique pas de sauts de branche, jmp, ce qui aurait une pénalité de performance significative si le résultat prévu n'est pas correct.
Alors, pourquoi un déménagement conditionnel fonctionne-t-il mieux?
Dans un processeur x86 typique, l'exécution d'une instruction est divisée en plusieurs étapes. En gros, nous avons différents matériels pour traiter différentes étapes. Nous n'avons donc pas besoin d'attendre la fin d'une instruction pour en commencer une nouvelle. C'est ce qu'on appelle le pipelining.
Dans un cas de branche, l'instruction suivante est déterminée par la précédente, nous ne pouvons donc pas faire de pipelining. Nous devons attendre ou prévoir.
Dans un cas de déménagement conditionnel,l'instruction de déplacement conditionnel d'exécution est divisée en plusieurs étapes, mais les étapes précédentes comme Fetch et Decode ne dépendent pas du résultat de l'instruction précédente; seules les dernières étapes ont besoin du résultat. Ainsi, nous attendons une fraction du temps d'exécution d'une instruction. C'est pourquoi la version de déplacement conditionnel est plus lente que la branche lorsque la prédiction est facile.
Le livre Computer Systems: A Programmer's Perspective, deuxième édition explique cela en détail. Vous pouvez consulter la section 3.6.6 pour les instructions de déplacement conditionnel, tout le chapitre 4 pour l'architecture du processeur et la section 5.11.2 pour le traitement spécial pour les sanctions de prédiction de branche et d'erreurs de prédiction.
Parfois, certains compilateurs modernes peuvent optimiser notre code en assemblage avec de meilleures performances, parfois certains compilateurs ne le peuvent pas (le code en question utilise le compilateur natif de Visual Studio). Connaître la différence de performances entre une branche et un déplacement conditionnel lorsqu'il est imprévisible peut nous aider à écrire du code avec de meilleures performances lorsque le scénario devient si complexe que le compilateur ne peut pas les optimiser automatiquement.
|
Si vous êtes curieux d'encore plus d'optimisations pouvant être apportées à ce code, considérez ceci:
En commençant par la boucle d'origine:
pour (non signé i = 0; i <100000; ++ i)
{
pour (unsigned j = 0; j  = 128)
somme + = données [j];
}
}
Avec l'échange de boucles, nous pouvons modifier en toute sécurité cette boucle en:
pour (unsigned j = 0; j  = 128)
somme + = données [j];
}
}
Ensuite, vous pouvez voir que le conditionnel if est constant tout au long de l'exécution de la boucle i, vous pouvez donc lever le if:
pour (unsigned j = 0; j  = 128)
{
pour (non signé i = 0; i <100000; ++ i)
{
somme + = données [j];
}
}
}
Ensuite, vous voyez que la boucle interne peut être réduite en une seule expression, en supposant que le modèle à virgule flottante le permette (/ fp: fast est lancé, par exemple)
pour (unsigned j = 0; j  = 128)
{
somme + = données [j] * 100000;
}
}
Celui-là est 100 000 fois plus rapide qu'avant.
|
Il ne fait aucun doute que certains d'entre nous seraient intéressés par des moyens d'identifier le code qui pose problème pour le prédicteur de branche du processeur. Le cachegrind de l'outil Valgrind a un simulateur de prédicteur de branche, activé à l'aide de l'indicateur --branch-sim = yes. L'exécuter sur les exemples de cette question, avec le nombre de boucles externes réduit à 10000 et compilé avec g ++, donne ces résultats:
Trié:
== 32551 == Succursales: 656.645.130 (656.609.208 cond + 35.922 ind)
== 32551 == Erreurs de pronostic: 169,556 (169,095 cond + 461 ind)
== 32551 == Taux d'erreur de lecture: 0,0% (0,0% + 1,2%)
Non trié:
== 32555 == Succursales: 655.996.082 (655.960.160 cond + 35.922 ind)
== 32555 == Erreurs de prédiction: 164073152 (164072692 cond + 460 ind)
== 32555 == Taux d'erreur de lecture: 25,0% (25,0% + 1,2%)
En explorant la sortie ligne par ligne produite par cg_annotate, nous voyons pour la boucle en question:
Trié:
Bc Bcm Bi Bim
10,001 4 0 0 pour (i non signé = 0; i <10000; ++ i)
. . . . {
. . . . // boucle primaire
327,690,000 10,016 0 0 pour (unsigned c = 0; c  = 128)
0 0 0 0 somme + = données [c];
. . . . }
. . . . }
Non trié:
Bc Bcm Bi Bim
10,001 4 0 0 pour (non signé i = 0; i <10000; ++ i)
. . . . {
. . . . // boucle primaire
327,690,000 10,038 0 0 pour (unsigned c = 0; c  = 128)
0 0 0 0 somme + = données [c];
. . . . }
. . . . }
Cela vous permet d'identifier facilement la ligne problématique - dans la version non triée, la ligne if (data [c]> = 128) est à l'origine de 164 050 007 branches conditionnelles mal prédites (Bcm) sous le modèle de prédicteur de branche de cachegrind, alors qu'elle n'en cause que 10 006 dans la version triée .
Alternativement, sous Linux, vous pouvez utiliser le sous-système des compteurs de performances pour accomplir la même tâche, mais avec des performances natives en utilisant des compteurs de CPU.
perf stat ./sumtest_sorted
Trié:
Statistiques du compteur de performances pour "./sumtest_sorted":
11808.095776 horloge de tâche # 0.998 CPU utilisés
1062 commutateurs de contexte # 0,090 K / s
14 migrations CPU # 0,001 K / s
337 défauts de page # 0,029 K / s
26,487,882,764 cycles # 2,243 GHz
41,025,654,322 instructions # 1,55 insns par cycle
6,558,871,379 succursales # 555,455 M / sec
567204 succursales manquées # 0,01% de toutes les succursales
11.827228330 secondes de temps écoulé
Non trié:
Performancestats de compteur pour './sumtest_unsorted':
28877.954344 horloge de tâche # 0.998 CPU utilisés
2584 commutateurs de contexte # 0,089 K / s
18 migrations CPU # 0,001 K / s
335 défauts de page # 0,012 K / s
65076127595 cycles # 2,253 GHz
41,032,528,741 instructions # 0,63 insns par cycle
6,560,579,013 succursales # 227,183 M / sec
1,646,394,749 succursales manquées # 25,10% de toutes les succursales
28,935500947 secondes de temps écoulé
Il peut également faire des annotations de code source avec désassemblage.
enregistrement de perf -e branch-misses ./sumtest_unsorted
perf annoter -d sumtest_unsorted
Pourcentage | Code source et désassemblage de sumtest_unsorted
------------------------------------------------
...
: somme + = données [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4.60: 400a26: cltq
0,00: 400a28: ajouter% rax, -0x30 (% rbp)
...
Consultez le didacticiel sur les performances pour plus de détails.
|
Je viens de lire sur cette question et ses réponses, et j'estime qu'il manque une réponse.
Un moyen courant d'éliminer la prédiction de branche qui, selon moi, fonctionne particulièrement bien dans les langages gérés est une recherche de table au lieu d'utiliser une branche (bien que je ne l'ai pas testé dans ce cas).
Cette approche fonctionne en général si:
c'est une petite table et est susceptible d'être mise en cache dans le processeur, et
vous exécutez les choses dans une boucle assez serrée et / ou le processeur peut précharger les données.
Contexte et pourquoi
Du point de vue du processeur, votre mémoire est lente. Pour compenser la différence de vitesse, quelques caches sont intégrés à votre processeur (cache L1 / L2). Alors imaginez que vous faites vos beaux calculs et que vous avez besoin d'un morceau de mémoire. Le processeur obtiendra son opération de «chargement» et charge la partie de la mémoire dans le cache - puis utilise le cache pour faire le reste des calculs. La mémoire étant relativement lente, cette «charge» ralentira votre programme.
Comme la prédiction de branche, cela a été optimisé dans les processeurs Pentium: le processeur prédit qu'il a besoin de charger une donnée et tente de la charger dans le cache avant que l'opération n'atteigne réellement le cache. Comme nous l'avons déjà vu, la prédiction de branche tourne parfois terriblement mal - dans le pire des cas, vous devez revenir en arrière et attendre une charge mémoire, ce qui prendra une éternité (en d'autres termes: l'échec de la prédiction de branche est mauvais, une mémoire charger après un échec de prédiction de branche est tout simplement horrible!).
Heureusement pour nous, si le modèle d'accès mémoire est prévisible, le processeur le chargera dans son cache rapide et tout va bien.
La première chose que nous devons savoir est ce qui est petit? Bien que plus petit soit généralement préférable, une règle de base est de s'en tenir aux tables de recherche d'une taille <= 4096 octets. En tant que limite supérieure: si votre table de recherche est supérieure à 64 Ko, cela vaut probablement la peine d'être reconsidéré.
Construire une table
Nous avons donc compris que nous pouvions créer une petite table. La prochaine chose à faire est de mettre en place une fonction de recherche. Les fonctions de recherche sont généralement de petites fonctions qui utilisent quelques opérations de base sur les nombres entiers (et, ou, xor, shift, add, remove et peut-être multiplier). Vous voulez que votre entrée soit traduite par la fonction de recherche en une sorte de «clé unique» dans votre table, qui vous donne alors simplement la réponse de tout le travail que vous vouliez qu'elle fasse.
Dans ce cas:> = 128 signifie que nous pouvons conserver la valeur, <128 signifie que nous nous en débarrassons. Le moyen le plus simple de le faire est d'utiliser un 'ET': si nous le gardons, nous le ET avec 7FFFFFFF; si nous voulons nous en débarrasser, nous ETons le avec 0. Notez également que 128 est une puissance de 2 - nous pouvons donc continuer et faire un tableau de 32768/128 entiers et le remplir avec un zéro et beaucoup de 7FFFFFFFF.
Langues gérées
Vous vous demandez peut-être pourquoi cela fonctionne bien dans les langues gérées. Après tout, les langages gérés vérifient les limites des tableaux avec une branche pour vous assurer de ne pas gâcher ...
Eh bien, pas exactement ... :-)
Il y a eu pas mal de travail sur l'élimination de cette branche pour les langages gérés. Par exemple:
pour (int i = 0; i  = 128)? c: 0;
}
// Test
DateTime startTime = System.DateTime.Now;
somme longue = 0;
pour (int i = 0; i <100000; ++ i)
{
// Boucle primaire
pour (int j = 0; j  = 128. Cela signifie que nous pouvons facilement extraire un seul bit qui nous dira si nous voulons une valeur ou non: en décalant les données vers la droite 7 bits, nous nous retrouvons avec un 0 bit ou un 1 bit, et nous ne voulons ajouter la valeur que lorsque nous avons 1 bit. Appelons ce bit le "bit de décision".
En utilisant la valeur 0/1 du bit de décision comme index dans un tableau, nous pouvons créer un code qui sera tout aussi rapide que les données soient triées ou non. Notre code ajoutera toujours une valeur, mais lorsque le bit de décision est 0, nous ajouterons la valeur à un endroit qui ne nous intéresse pas. Voici le code:
// Test
clock_t start = horloge ();
long long a [] = {0, 0};
longue somme longue;
pour (non signé i = 0; i <100000; ++ i)
{
// Boucle primaire
pour (non signé c = 0; c > 7);
a [j] + = données [c];
}
}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
somme = a [1];
Ce code gaspille la moitié des ajouts mais n'a jamais d'échec de prédiction de branche. C'est extrêmement plus rapide sur des données aléatoires que la version avec une instruction if réelle.
Mais dans mes tests, une table de recherche explicite était légèrement plus rapide que cela, probablement parce que l'indexation dans une table de recherche était légèrement plus rapide que le transfert de bits. Cela montre comment mon code met en place et utilise la table de recherche (appelée sans imagination lut pour "LookUp Table" dans le code). Voici le code C ++:
// Déclarez puis remplissez la table de recherche
int lut [256];
pour (non signé c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Utilise la table de recherche après sa construction
pour (non signé i = 0; i <100000; ++ i)
{
// Boucle primaire
pour (non signé c = 0; c )
node = node-> pLeft;
autre
node = node-> pRight;
cette bibliothèque ferait quelque chose comme:
i = (x  valeur);
nœud = nœud-> lien [i];
Voici un lien vers ce code: Red Black Trees, Eternally Confuzzled
|
Dans le cas trié, vous pouvez faire mieux que de vous fier à une prédiction de branche réussie ou à une astuce de comparaison sans branche: supprimez complètement la branche.
En effet, le tableau est partitionné dans une zone contiguë avec des données <128 et une autre avec des données> = 128. Vous devriez donc trouver le point de partition avec une recherche dichotomique (en utilisant Lg (arraySize) = 15 comparaisons), puis faire une accumulation directe à partir de ce point.
Quelque chose comme (non coché)
int i = 0, j, k = taille du tableau;
tandis que (i > 1;
if (données [j]> = 128)
k = j;
autre
i = j;
}
somme = 0;
pour (; i > 1;
pour (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
pour (somme = 0; i  = 128)
/ \
/ \
/ \
vrai faux
/ \
/ \
/ \
/ \
B) somme + = données [c]; C) pour boucle ou print ().
Sans prédiction de branche, les événements suivants se produiraient:
Pour exécuter l'instruction B ou l'instruction C, le processeur devra attendre que l'instruction A n'atteigne pas l'étape EX du pipeline, car la décision d'aller à l'instruction B ou à l'instruction C dépend du résultat de l'instruction A. Donc le pipeline ressemblera à ceci.
quand si la condition retourne vrai:
Quand si la condition retourne false:
En raison de l'attente du résultat de l'instruction A, le nombre total de cycles CPU passés dans le cas ci-dessus (sans prédiction de branchement; pour vrai et faux) est de 7.
Alors, qu'est-ce que la prédiction de branche?
Le prédicteur de branche essaiera de deviner dans quelle direction une branche (une structure if-then-else) ira avant que cela ne soit connu avec certitude. Il n'attendra pas que l'instruction A atteigne l'étape EX du pipeline, mais il devinera la décision et ira à cette instruction (B ou C dans le cas de notre exemple).
En cas de supposition correcte, le pipeline ressemble à ceci:
S'il est détecté plus tard que la supposition était erronée, les instructions partiellement exécutées sont ignorées et le pipeline recommence avec la branche correcte, ce qui entraîne un retard.
Le temps perdu en cas d'erreur de prédiction de branchement est égal au nombre d'étapes dans le pipeline de l'étape d'extraction à l'étape d'exécution. Les microprocesseurs modernes ont tendance à avoir des pipelines assez longs de sorte que le délai de prédiction erronée se situe entre 10 et 20 cycles d'horloge. Plus le pipeline est long, plus le besoin d'un bon prédicteur de branchement est grand.
Dans le code de l'OP, la première fois que le conditionnel, le prédicteur de branche n'a aucune information pour baser la prédiction, donc la première fois, il choisira au hasard l'instruction suivante. Plus tard dans la boucle for, il peut baser la prédiction sur l'historique.
Pour un tableau trié par ordre croissant, il existe trois possibilités:
Tous les éléments sont inférieurs à 128
Tous les éléments sont supérieurs à 128
Certains nouveaux éléments de départ sont inférieurs à 128 et plus tard, ils deviennent supérieurs à 128
Supposons que le prédicteur assumera toujours la vraie branche lors de la première exécution.
Donc dans le premier cas, il faudra toujours le vraibranche puisque historiquement toutes ses prédictions sont correctes.
Dans le 2ème cas, au départ, il prédira mal, mais après quelques itérations, il prédira correctement.
Dans le 3ème cas, il prédira initialement correctement jusqu'à ce que les éléments soient inférieurs à 128. Après quoi, il échouera pendant un certain temps et se corrigera lui-même lorsqu'il verra un échec de prédiction de branche dans l'historique.
Dans tous ces cas, l'échec sera trop peu nombreux et par conséquent, il ne sera nécessaire que quelques fois de rejeter les instructions partiellement exécutées et de recommencer avec la branche correcte, ce qui réduira le nombre de cycles CPU.
Mais dans le cas d'un tableau aléatoire non trié, la prédiction devra ignorer les instructions partiellement exécutées et recommencer avec la branche correcte la plupart du temps et entraîner plus de cycles CPU par rapport au tableau trié.
|
Une réponse officielle serait de
Intel - Éviter le coût des erreurs de prédiction de succursale
Intel - Réorganisation des succursales et des boucles pour éviter les erreurs de pronostic
Articles scientifiques - Architecture informatique de prédiction de branche
Livres: J.L. Hennessy, D.A. Patterson: Architecture informatique: une approche quantitative
Articles dans des publications scientifiques: T.Y. Ouais, Y.N. Patt en a fait beaucoup sur les prédictions des branches.
Vous pouvez également voir sur ce joli diagramme pourquoi le prédicteur de branche est confus.
Chaque élément du code d'origine est une valeur aléatoire
données [c] = std :: rand ()% 256;
donc le prédicteur changera de côté lorsque std :: rand () soufflera.
D'un autre côté, une fois trié, le prédicteur passera d'abord dans un état de fortement non pris et lorsque les valeurs passeront à la valeur élevée, le prédicteur changera en trois passages de fortement non pris à fortement pris.
|
Dans la même ligne (je pense que cela n'a été souligné par aucune réponse), il est bon de mentionner que parfois (en particulier dans les logiciels où les performances comptent - comme dans le noyau Linux), vous pouvez trouver des instructions if comme celles-ci:
si (probablement (tout_is_ok))
{
/* Faire quelque chose */
}
ou de manière similaire:
if (peu probable (condition_très_improbable))
{
/* Faire quelque chose */
}
Probable () et improbable () sont en fait des macros qui sont définies en utilisant quelque chose comme __builtin_expect du GCC pour aider le compilateur à insérer du code de prédiction pour favoriser la condition en tenant compte des informations fournies par l'utilisateur. GCC supporte d'autres builtins qui pourraient changer le comportement du programme en cours d'exécution ou émettre des instructions de bas niveau comme vider le cache, etc. Voir cette documentation qui passe par les builtins disponibles de GCC.
Normalement, ce type d'optimisation se trouve principalement dans les applications en temps réel dur ou les systèmes embarqués où le temps d'exécution est important et critique. Par exemple, si vous recherchez une condition d'erreur qui ne se produit que 1/10000000 fois, pourquoi ne pas en informer le compilateur? De cette façon, par défaut, la prédiction de branche supposerait que la condition est fausse.
|
Les opérations booléennes fréquemment utilisées en C ++ produisent de nombreuses branches dans le programme compilé. Si ces branches sont à l'intérieur de boucles et sont difficiles à prévoir, elles peuvent ralentir considérablement l'exécution. Les variables booléennes sont stockées sous forme d'entiers 8 bits avec la valeur 0 pour faux et 1 pour vrai.
Les variables booléennes sont surdéterminées en ce sens que tous les opérateurs qui ont des variables booléennes en entrée vérifient si les entrées ont une autre valeur que 0 ou 1, mais les opérateurs qui ont des booléens en sortie ne peuvent produire aucune autre valeur que 0 ou 1. Cela rend les opérations avec Les variables booléennes en entrée sont moins efficaces que nécessaire.
Prenons l'exemple:
booléen a, b, c, d;
c = a && b;
d = a || b;
Ceci est généralement implémenté par le compilateur de la manière suivante:
booléen a, b, c, d;
si (a! = 0) {
si (b! = 0) {
c = 1;
}
autre {
goto CFALSE;
}
}
autre {
CFALSE:
c = 0;
}
si (a == 0) {
si (b == 0) {
d = 0;
}
autre {
goto DTRUE;
}
}
autre {
DTRUE:
d = 1;
}
Ce code est loin d'être optimal. Les succursales peuvent prendre du temps en cas d'erreurs de prédiction. Les opérations booléennes peuvent être rendues beaucoup plus efficaces si l'on sait avec certitude que les opérandes n'ont pas d'autres valeurs que 0 et 1. La raison pour laquelle le compilateur ne fait pas une telle hypothèse est que les variables peuvent avoir d'autres valeurs si elles ne sont pas initialisées ou proviennent de sources inconnues. Le code ci-dessus peut être optimisé si a et b ont été initialisés à des valeurs valides ou s'ils proviennent d'opérateurs qui produisent une sortie booléenne. Le code optimisé ressemble à ceci:
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char est utilisé à la place de bool afin de permettre d'utiliser les opérateurs binaires (& et |) au lieu des opérateurs booléens (&& et ||). Les opérateurs au niveau du bit sont des instructions uniques qui ne prennent qu'un seul cycle d'horloge. L'opérateur OR (|) fonctionne même si a et b ont d'autres valeurs que 0 ou 1. L'opérateur AND (&) et l'opérateur OU EXCLUSIF (^) peuvent donner des résultats incohérents si les opérandes ont d'autres valeurs que 0 et 1.
~ ne peut pas être utilisé pour NOT. Au lieu,vous pouvez créer un NOT booléen sur une variable connue pour être 0 ou 1 en XOR avec 1:
booléen a, b;
b =! a;
peut être optimisé pour:
char a = 0, b;
b = a ^ 1;
a && b ne peut pas être remplacé par a & b si b est une expression qui ne doit pas être évaluée si a est faux (&& n'évaluera pas b, & will). De même, un || b ne peut pas être remplacé par a | b si b est une expression qui ne doit pas être évaluée si a est vrai.
L'utilisation d'opérateurs au niveau du bit est plus avantageuse si les opérandes sont des variables que si les opérandes sont des comparaisons:
bool a; double x, y, z;
a = x> y && z <5,0;
est optimal dans la plupart des cas (sauf si vous vous attendez à ce que l'expression && génère de nombreuses erreurs de prédiction de branche).
|
Ça c'est sûr!...
La prédiction de branche rend la logique plus lente, à cause de la commutation qui se produit dans votre code! C'est comme si vous alliez dans une rue droite ou une rue avec beaucoup de virages, c'est sûr que la droite va se faire plus vite! ...
Si le tableau est trié, votre condition est fausse à la première étape: data [c]> = 128, devient alors une valeur vraie pour tout le trajet jusqu'au bout de la rue. C'est ainsi que vous arrivez plus rapidement au bout de la logique. D'un autre côté, en utilisant un tableau non trié, vous avez besoin de beaucoup de retournement et de traitement qui ralentissent certainement votre code ...
Regardez l'image que j'ai créée pour vous ci-dessous. Quelle rue sera terminée le plus rapidement?
Donc, par programmation, la prédiction de branche ralentit le processus ...
À la fin également, il est bon de savoir que nous avons deux types de prédictions de branche qui affecteront chacune votre code différemment:
1. Statique
2. Dynamique
La prédiction de branche statique est utilisée par le microprocesseur la première fois
une branche conditionnelle est rencontrée et la prédiction de branche dynamique est
utilisé pour les exécutions successives du code de branche conditionnel.
Afin d'écrire efficacement votre code pour profiter de ces
règles, lors de l'écriture d'instructions if-else ou switch, vérifiez le plus
les cas communs en premier et de travailler progressivement vers le moins commun.
Les boucles ne nécessitent pas nécessairement de commande spéciale de code pour
prédiction de branche statique, comme seule condition de l'itérateur de boucle
est normalement utilisé.
|
Cette question a déjà reçu une excellente réponse à plusieurs reprises. J'aimerais néanmoins attirer l'attention du groupe sur une autre analyse intéressante.
Récemment, cet exemple (très légèrement modifié) a également été utilisé comme moyen de démontrer comment un morceau de code peut être profilé dans le programme lui-même sous Windows. En cours de route, l'auteur montre également comment utiliser les résultats pour déterminer où le code passe la plupart de son temps dans le cas trié et non trié. Enfin, l'article montre également comment utiliser une fonctionnalité peu connue de HAL (Hardware Abstraction Layer) pour déterminer à quel point les erreurs de prédiction de branche se produisent dans le cas non trié.
Le lien est ici:
Une démonstration d'auto-profilage
|
Comme ce qui a déjà été mentionné par d'autres, ce qui se cache derrière le mystère est Branch Predictor.
Je n'essaye pas d'ajouter quelque chose mais d'expliquer le concept d'une autre manière.
Il y a une introduction concise sur le wiki qui contient du texte et un diagramme.
J'aime l'explication ci-dessous qui utilise un diagramme pour élaborer intuitivement le prédicteur de branche.
Dans l'architecture informatique, un prédicteur de branche est un
circuit numérique qui essaie de deviner dans quel sens une branche (par exemple, une
if-then-else) ira avant que cela ne soit connu avec certitude. le
l'objectif du prédicteur de branchement est d'améliorer le débit dans le
pipeline d'instructions. Les prédicteurs de branche jouent un rôle essentiel dans
obtenir des performances efficaces élevées dans de nombreux canalisations modernes
architectures de microprocesseur telles que x86.
Le branchement bidirectionnel est généralement implémenté avec un saut conditionnel
instruction. Un saut conditionnel peut être "non effectué" et continuer
exécution avec la première branche de code qui suit immédiatement
après le saut conditionnel, ou il peut être "pris" et passer à un
endroit différent dans la mémoire du programme où se trouve la deuxième branche de code
stocké. On ne sait pas avec certitude si un saut conditionnel sera
prises ou non prises jusqu'à ce que la condition ait été calculée et que le
le saut conditionnel a passé l'étape d'exécution dans l'instruction
canalisation (voir fig.1).
Sur la base du scénario décrit, j'ai écrit une démo d'animation pour montrer comment les instructions sont exécutées dans un pipeline dans différentes situations.
Sans le prédicteur de branche.
Sans prédiction de branche, le processeur devrait attendre que le
l'instruction de saut conditionnel a passé l'étape d'exécution avant que
l'instruction suivante peut entrer dans l'étape d'extraction dans le pipeline.
L'exemple contient trois instructions et la première est une instruction de saut conditionnel. Les deux dernières instructions peuvent entrer dans le pipeline jusqu'à ce que l'instruction de saut conditionnel soit exécutée.
Il faudra 9 cycles d'horloge pour que 3 instructions soient terminées.
Utilisez Branch Predictor et ne faites pas de saut conditionnel. Supposons que le pronostic ne prend pas lesaut conditionnel.
Il faudra 7 cycles d'horloge pour que 3 instructions soient terminées.
Utilisez Branch Predictor et effectuez un saut conditionnel. Supposons que le prédicteur n'effectue pas le saut conditionnel.
Il faudra 9 cycles d'horloge pour que 3 instructions soient terminées.
Le temps perdu en cas d'erreur de prédiction de branche est égal à
le nombre d'étapes dans le pipeline de l'étape d'extraction à l'étape
exécuter l'étape. Les microprocesseurs modernes ont tendance à avoir des
pipelines de sorte que le délai de mauvaise prédiction soit compris entre 10 et 20 heures
cycles. Par conséquent, l'allongement d'un pipeline augmente le besoin d'un
prédicteur de branche plus avancé.
Comme vous pouvez le voir, il semble que nous n'avons pas de raison de ne pas utiliser Branch Predictor.
C'est une démo assez simple qui clarifie la partie très basique de Branch Predictor. Si ces gifs sont ennuyeux, n'hésitez pas à les supprimer de la réponse et les visiteurs peuvent également obtenir le code source de la démo en direct de BranchPredictorDemo
|
Gain de prédiction de branche!
Il est important de comprendre que les erreurs de prédiction des branches ne ralentissent pas les programmes. Le coût d'une prédiction manquée est comme si la prédiction de branche n'existait pas et que vous attendiez l'évaluation de l'expression pour décider du code à exécuter (plus d'explications dans le paragraphe suivant).
if (expression)
{
// Exécuter 1
} autre {
// Exécuter 2
}
Chaque fois qu'il y a une instruction if-else \ switch, l'expression doit être évaluée pour déterminer quel bloc doit être exécuté. Dans le code d'assemblage généré par le compilateur, des instructions de branche conditionnelle sont insérées.
Une instruction de branchement peut amener un ordinateur à commencer à exécuter une séquence d'instructions différente et ainsi à s'écarter de son comportement par défaut d'exécution des instructions dans l'ordre (c'est-à-dire si l'expression est fausse, le programme saute le code du bloc if) en fonction d'une condition, qui est l'expression évaluation dans notre cas.
Cela étant dit, le compilateur essaie de prédire le résultat avant qu'il ne soit réellement évalué. Il récupérera les instructions du bloc if, et si l'expression s'avère vraie, alors merveilleux! Nous avons gagné le temps qu'il fallait pour l'évaluer et avons progressé dans le code; sinon, nous exécutons le mauvais code, le pipeline est vidé et le bon bloc est exécuté.
Visualisation:
Disons que vous devez choisir l'itinéraire 1 ou l'itinéraire 2. En attendant que votre partenaire vérifie la carte, vous vous êtes arrêté à ## et vous avez attendu, ou vous pouvez simplement choisir l'itinéraire1 et si vous avez eu de la chance (l'itinéraire 1 est l'itinéraire correct), alors génial vous n'avez pas eu à attendre que votre partenaire vérifie la carte (vous avez économisé le temps qu'il lui aurait fallu pour vérifier la carte), sinon vous reviendrez simplement.
Si le rinçage des pipelines est très rapide, aujourd'hui, ce pari en vaut la peine. Prédire des données triées ou des données qui changent lentement est toujours plus facile et mieux que de prévoir des changements rapides.
O Route 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Route 2 \ --------------------------------
|
Sur ARM, aucune branche n'est nécessaire, car chaque instruction a un champ de condition de 4 bits, qui teste (à un coût nul) l'une des 16 conditions différentes pouvant survenir dans le registre d'état du processeur, et si la condition d'une instruction est false, l'instruction est ignorée. Cela élimine le besoin de branches courtes et il n'y aurait pas de succès de prédiction de branche pour cet algorithme. Par conséquent, la version triée de cet algorithme s'exécuterait plus lentement que la version non triée sur ARM, en raison de la surcharge supplémentaire du tri.
La boucle interne de cet algorithme ressemblerait à ce qui suit en langage d'assemblage ARM:
MOV R0, # 0 // R0 = somme = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = addr of data array (place cette instruction en dehors de la boucle externe)
.inner_loop // Etiquette de branche de boucle intérieure
LDRB R3, [R2, R1] // R3 = données [c]
CMP R3, # 128 // comparer R3 à 128
AJOUTER R0, R0, R3 // si R3> = 128, alors somme + = données [c] - aucune branche nécessaire!
AJOUTER R1, R1, # 1 // c ++
CMP R1, #arraySize // compare c à arraySize
BLT inner_loop // Branchement vers inner_loop si c  ());
pour (non signé c = 0; c  = 128
somme = somme + données1 (j);
fin
fin
fin
toc;
ExeTimeWithSorting = toc - tic;
Les résultats pour le code MATLAB ci-dessus sont les suivants:
a: Temps écoulé (sans tri) = 3479,880861 secondes.
b: Temps écoulé (avec tri) = 2377,873098 secondes.
Les résultats du code C comme dans @GManNickG j'obtiens:
a: Temps écoulé (sans tri) = 19,8761 sec.
b: Temps écoulé (avec tri) = 7,37778 sec.
Sur cette base, il semble que MATLAB soit presque 175 fois plus lent que l'implémentation C sans tri et 350 fois plus lent avec le tri. En d'autres termes, l'effet (de la prédiction de branche) est de 1,46x pour l'implémentation MATLAB et de 2,7x pour l'implémentation C.
|
L'hypothèse par d'autres réponses qu'il faut trier les données n'est pas correcte.
Le code suivant ne trie pas l'intégralité du tableau, mais uniquement des segments de 200 éléments, et s'exécute ainsi le plus rapidement.
Le tri uniquement des sections à k éléments complète le prétraitement en temps linéaire, O (n), plutôt qu'en temps O (n.log (n)) nécessaire pour trier le tableau entier.
#include 
#include 
#include 
int main() {
données int [32768]; const int l = taille des données / taille des données [0];
pour (non signé c = 0; c  = 128)
somme + = données [c];
}
}
std :: cout << static_cast  (clock () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "somme =" << somme << std :: endl;
}
Cela "prouve" également que cela n'a rien à voir avec un problème algorithmique tel que l'ordre de tri, et il s'agit bien d'une prédiction de branche.
|
Réponse de Bjarne Stroustrup à cette question:
Cela ressemble à une question d'entrevue. Est-ce vrai? Comment saurais tu? C'est une mauvaise idée de répondre aux questions sur l'efficacité sans d'abord faire quelques mesures, il est donc important de savoir comment mesurer.
Donc, j'ai essayé avec un vecteur d'un million d'entiers et j'ai obtenu:
Déjà trié 32995 millisecondes
Mélangé 125944 millisecondes
Déjà trié 18610 millisecondes
Mélangé 133304 millisecondes
Déjà trié 17942 millisecondes
Mélangé 107858 millisecondes
J'ai couru ça plusieurs fois pour être sûr. Oui, le phénomène est réel. Mon code clé était:
void run (vector  & v, const string & label)
{
auto t0 = horloge_système :: maintenant ();
sort (v.begin (), v.end ());
auto t1 = horloge_système :: maintenant ();
cout << label
<< durée_cast  (t1 - t0) .count ()
<< "millisecondes \ n";
}
void tst ()
{
vecteur  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "déjà trié");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
run (v, "mélangé");
}
Au moins, le phénomène est réel avec ce compilateur, cette bibliothèque standard et ces paramètres d'optimisation. Différentes implémentations peuvent donner et donnent des réponses différentes. En fait, quelqu'un a fait une étude plus systématique (une recherche rapide sur le Web le trouvera) et la plupart des implémentations montrent cet effet.
Une des raisons est la prédiction de branche: l'opération clé dans l'algorithme de tri est «si (v [i]  = 128. Cela signifie que nous pouvons facilement extraire un seul bit qui nous dira si nous voulons une valeur ou non: en décalant les données vers la droite 7 bits, nous nous retrouvons avec un 0 bit ou un 1 bit, et nous ne voulons ajouter la valeur que lorsque nous avons 1 bit. Appelons ce bit le "bit de décision".
En utilisant la valeur 0/1 du bit de décision comme index dans un tableau, nous pouvons créer un code qui sera tout aussi rapide que les données soient triées ou non. Notre code ajoutera toujours une valeur, mais lorsque le bit de décision est 0, nous ajouterons la valeur à un endroit qui ne nous intéresse pas. Voici le code:
// Test
clock_t start = horloge ();
long long a [] = {0, 0};
longue somme longue;
pour (non signé i = 0; i <100000; ++ i)
{
// Boucle primaire
pour (non signé c = 0; c > 7);
a [j] + = données [c];
}
}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
somme = a [1];
Ce code gaspille la moitié des ajouts mais n'a jamais d'échec de prédiction de branche. C'est extrêmement plus rapide sur des données aléatoires que la version avec une instruction if réelle.
Mais dans mes tests, une table de recherche explicite était légèrement plus rapide que cela, probablement parce que l'indexation dans une table de recherche était légèrement plus rapide que le transfert de bits. Cela montre comment mon code met en place et utilise la table de recherche (appelée sans imagination lut pour "LookUp Table" dans le code). Voici le code C ++:
// Déclarez puis remplissez la table de recherche
int lut [256];
pour (non signé c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Utilise la table de recherche après sa construction
pour (non signé i = 0; i <100000; ++ i)
{
// Boucle primaire
pour (non signé c = 0; c )
node = node-> pLeft;
autre
node = node-> pRight;
cette bibliothèque ferait quelque chose comme:
i = (x  valeur);
nœud = nœud-> lien [i];
C'est une bonne solution et peut-être que cela fonctionnera.
|
Question très active. Gagnez 10 points de réputation pour répondre à cette question. L'exigence de réputation permet de protéger cette question contre les spams et les activités sans réponse.
Ce n'est pas la réponse que vous recherchez? Parcourez les autres questions étiquetées java c ++ optimisation des performances prédiction de branche ou posez votre propre question.